HashSet 底層原理

• 底層採用哈希表存儲

• 哈希表是一種對於增刪改查數據性能都比較好的結構

• 組成

  • JDK8 之前：數組＋鍊表
  • JDK8 之後：數組＋鍊表＋紅黑樹

• 哈希值

  • 對象的整數表現形式
  • 公式：
    • int index = (數組長度 - 1) & 哈希值
  • 根據hashCode方法計算出來
  • 定義在Object中，所有對象都可以調用，默認使用地址值進行計算
  • 一般情況下會重寫hashCode方法，利用對象內部的屬性計算哈希值

• 對象的哈希值特點

  • 若沒有重寫hashCode方法，不同對象算出來的哈希值不同
  • 若重寫hashCode方法，就算不同對象，只要屬性值相同，算出來就是一樣的
  • 少部分情況，不同的屬性值或者不同的地址值算出來的哈希值也有可能一樣（哈希碰撞）

• JDK8之前的HashSet原理

  • 
  • 
  • 如果同一位置上有一個鍊表，則會沿著鍊表逐一使用equals比對，直到走到底添加或者是找到一樣內容的就不添加
  • 加載因子：
    • 會用默認長度乘上加載因子，作為擴容的標準
    • 本例默認長度為16, 16x0.75 = 12,也就是一旦內容物裝到12個時就會擴容
    • 擴容為原長度2倍

• JDK8之後

  • 當鍊表長度大於8且數組長度大於64（同時滿足兩個條件）
  • 當前鍊表會轉為紅黑樹
  • 

• 若集合中存的是自定義對象，必須要重寫equals跟hashCode方法

  • 我們希望equals比的是對象的內容是否相同
  • 同時也希望hashCode方法是根據對象內容產生hash值而不是透過地址產生